from random import randint


"""
题目:把一个数组最开始的若干个元素搬到数组的末尾，我们称之为
数组的旋转。输入一个递增排序的数组的一个 旋转，输出旋转数组的最小
元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一一个旋转，该数组的最小
值为1。

"""


def my_min_rotatearr(arr):
    # 倒过来遍历，非递减时取得最小值, 这种方式的复杂度是O(n)
    pre = arr[-1]
    n = len(arr)

    for i in range(n-2, -1, -1):
        if pre < arr[i]:
            return pre
        pre = arr[i]

    return pre


def min_rotatearr(arr):
    # 采用二分查找的方式, 复杂度O(logn)
    lo = 0
    high = len(arr) - 1

    while lo < high:
        mid = (lo + high) // 2
        if arr[mid] < arr[high]:
            # 如果arr[mid] < arr[high], 则最小值在[lo, mid]
            high = mid
        elif arr[mid] > arr[high]:
            # 如果arr[mid] > arr[high], 则最小值在[mid+1, high]
            lo = mid + 1
        else:
            # 如果arr[mid] == arr[high], 分为两种情况mid = high -1, mid < high -1
            high -= 1
    return arr[lo]


if __name__ == "__main__":
    # 随机测试
    for _ in range(100000):
        n = randint(5, 15)
        arr = []
        for i in range(n):
            arr.append(randint(0, 10))
        arr.sort()
        # 随机分割点
        k = randint(0, n)
        test_arr = arr[k:] + arr[:k]
        pre_min_num = min_rotatearr(test_arr)
        
        if pre_min_num != arr[0]:
            print("erro")
            print(test_arr, arr, pre_min_num)

